package sort;

import java.util.Arrays;

public class MergeSort {

	//归并排序
	public static void mergeSort(int[] arr,int start,int end) {
		//中间下标
		int middle = (start+end)/2;

		if(start < end) {
			//递归：左边数组排序
			mergeSort(arr,start,middle);
			//递归：右边数组排序
			mergeSort(arr,middle+1,end);

			merge(arr, start,middle, end);
		}
	}

	public static void merge(int[] arr,int start, int middle,int end){

		//存储归并后的临时数据
		int[] temp = new int[end-start+1];
		//第一个数组中需要遍历的下标
		int i = start;
		//第二个数组中需要遍历的下标
		int j = middle+1;
		//索引下标
		int index = 0;
		while(i<=middle && j<=end) {
			if(arr[i]<=arr[j]) {
				temp[index] = arr[i];
				i++;
			}else {
				temp[index] = arr[j];
				j++;
			}
			index++;
		}
		while(i<=middle) {
			temp[index] = arr[i];
			i++;
			index++;
		}
		while(j<=end) {
			temp[index] = arr[j];
			j++;
			index++;
		}

//		System.arraycopy(temp, 0, arr, start, end-start+1);
		for(int k=0;k<temp.length;k++) {
			arr[k+start] = temp[k];
		}

		System.out.println(Arrays.toString(arr));

	}

	public static void main(String[] args) {
		int[] a = new int[] {9,1,5,9,8,9,3};
		for(int aa:a) {
			System.out.print(aa+" ");
		}
		System.out.println();
		mergeSort(a,0,a.length-1);
	}

}

/**
 * 归并排序
 * @param arr
 * @param start
 * @param end

void merge(int[] arr, int start, int end) {
if(start == end)	return ;
int mid = start+(end-start)/2;
//左小有序
merge(arr,start,mid);
//右大有序
merge(arr,mid+1,end);

int[] temp = new int[end-start+1];
int i = start, j = mid+1, k = 0;
while(i <= mid && j <= end)
temp[k++] = arr[i]<arr[j]?arr[i++]:arr[j++];
//左边剩余的排序
while(i <= mid)
temp[k++] = arr[i++];
//右边剩余的排序
while(j < end)
temp[k++] = arr[j+1];

System.arraycopy(temp,0,arr,start,end);
}
 */
